package 代码随想2._1数组;

import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;

/**
 * @author XXX
 * @date 2024-01-11 13:23
 */

class Test{

}

/**
 * https://leetcode.cn/problems/binary-search/description/
 * */
public class _1二分查找 {
    public int search(int[] nums, int target) {
        int left = 0 , right = nums.length-1;
        while (left<=right){
            int mid = (left + right) / 2;  // int mid = left + ((right - left) >> 1);
            if(nums[mid] == target)
                return mid;
            else if(nums[mid]>target)
                right = mid -1;
            else
                left = mid + 1;
        }
        return -1;
    }
}

/**
 * https://leetcode.cn/problems/search-insert-position/
 */
class 搜索插入位置{
    public int searchInsert(int[] nums, int target) {
        int left = 0 , right  = nums.length -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return  mid;
        }
        return right + 1;
    }
}

/**
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 */
class 在排序数组中查找元素的第一个和最后一个位置{
    /**
     * 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
     * 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
     * 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
     */
    public int[] searchRange(int[] nums, int target) {
        int lefBoder = getLeftBoder(nums , target);
        int rightBoder = getRightBorder(nums, target);
        //情况一
        if(lefBoder == -2 || rightBoder == -2)  return new int[]{-1,-1};
        //情况三
        else if(rightBoder - lefBoder > 1 ) return new int[]{lefBoder + 1, rightBoder - 1};
        //情况二
        else return new int[]{-1,-1};
    }

    int getRightBorder(int[] nums, int target){
        int left = 0 , right = nums.length - 1;
        int rightBoder = -2;
        while (left<=right){
            int mid = left + ((right - left)>>2);
            if(nums[mid]<=target){
                left = mid + 1;
                rightBoder = left;
            }else{
                right = mid - 1;
            }
        }
        return rightBoder;
    }

    int getLeftBoder(int[] nums, int target){
        int left = 0 , right = nums.length - 1;
        int leftBoder = -2;
        while (left<=right){
            int mid = left + ((right - left)>>2);
            if(nums[mid]>=target){
                right = mid - 1;
                leftBoder = right;
            }else{
                left = mid + 1;
            }
        }
        return leftBoder;
    }


    public int[] searchRange2(int[] nums, int target) {
        int index = binarySearch(nums, target); // 二分查找

        if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1}
            return new int[] {-1, -1}; // 匿名数组
        }
        // nums 中存在 targe，则左右滑动指针，来找到符合题意的区间
        int left = index;
        int right = index;
        // 向左滑动，找左边界
        while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止数组越界。逻辑短路，两个条件顺序不能换
            left--;
        }
        // 向右滑动，找右边界
        while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止数组越界。
            right++;
        }
        return new int[] {left, right};
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     */
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 不变量：左闭右闭区间

        while (left <= right) { // 不变量：左闭右闭区间
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1; // 不变量：左闭右闭区间
            }
        }
        return -1; // 不存在
    }
}

/**
 * https://leetcode.cn/problems/sqrtx/
 */
class x的平方根 {
    public int mySqrt(int x) {
        int left = 0 , right = x , ans = -1;
        while (left<=right){
            int mid = left + ((right - left) >> 2);
            if((long) mid * mid <= x){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return  ans;
    }
}

/**
 * https://leetcode.cn/problems/valid-perfect-square/description/
 */
class 有效的完全平方数{
    public boolean isPerfectSquare(int num) {
        int left = 0 , right = num;
        while (left <= right){
            int mid = left + ((right - left) >> 2);
            if((long) mid * mid == num)
                return true;
            else if((long) mid * mid > num)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return  false;
    }
}